﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WordNet.Core.Graph
{
    // This implementation uses depth-first search.
    public class DirectedCycle:IDirectedCycle
    {
        Dictionary<int, bool> _marked;
        // previous vertex on path to v
        Dictionary<int, int> _previous;
        Dictionary<int, bool> _onStack;
        // directed cycle
        Stack<int> _cycle;

        public DirectedCycle(IDigraph g)
        {
            Init(g);
            foreach (var vertex in g.GetAllVertices())
            {
                if (!IsMarked(vertex))
                    FindCycle(g, vertex);
            }
        }

        public bool HasCycle
        {
            get { return _cycle != null; }
        }

        public IEnumerable<int> Cycle
        {
            get { return _cycle; }
        }

        // dfs
        private void FindCycle(IDigraph g, int vertex)
        {
            OnStack(vertex);
            Mark(vertex);
            foreach (int w in g.AdjacencyList(vertex))
            {
                if (Cycle != null)
                    return;
                else if (!IsMarked(w))
                {
                    // found unvisited vertex
                    
                    EdgeTo(w, vertex);
                    // follow the path
                    FindCycle(g, w);
                }
                else if (IsOnStack(w))
                {
                    // found cycle
                    _cycle = new Stack<int>();
                    for (int x = vertex; x != w; x = _previous[x])
                        _cycle.Push(x);
                    _cycle.Push(w);
                    _cycle.Push(vertex);
                }
            }
            _onStack[vertex] = false;
        }

        private void Init(IDigraph g)
        {
            _marked = new Dictionary<int, bool>(g.NumberOfVertices);
            _previous = new Dictionary<int, int>(g.NumberOfVertices);
            _onStack = new Dictionary<int, bool>(g.NumberOfVertices);
        }
        
        private bool IsOnStack(int v)
        {
            return _onStack.ContainsKey(v) && _onStack[v];
        }

        private void OnStack(int v)
        {
            if (!_onStack.ContainsKey(v))
                _onStack.Add(v, false);
            _onStack[v] = true;
        }

        private bool IsMarked(int v)
        {
            return _marked.ContainsKey(v) && _marked[v];
        }

        private void Mark(int v)
        {
            if (!_marked.ContainsKey(v))
                _marked.Add(v, false);
            _marked[v] = true;
        }

        private void EdgeTo(int w, int v)
        {
            if (!_previous.ContainsKey(w))
                _previous.Add(w, 0);
            _previous[w] = v; 
        }
       
        
    }
}
